package practice.sort.compare;

import practice.sort.Sort;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/8/10 11:43
 */
public class HeapSort extends Sort {
    int heapSize;
    @Override
    public void sort() {
        heapSize = nums.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
        while (heapSize > 0) {
            swap(0, --heapSize);
            siftDown(0);
        }
    }

    public void siftDown(int index) {
        int half = heapSize >> 1;
        int val = nums[index];
        while (index < half) {
            int childIndex = (index << 1) + 1; // 左子树
            int child = nums[childIndex];
            int rightIndex = childIndex + 1;
            if (rightIndex < heapSize && nums[rightIndex] > child) {
                child = nums[childIndex = rightIndex];
            }
            if (child <= val) break;
            swap(index, childIndex);
            index = childIndex;
        }
        nums[index] = val;
    }
}
